/**
 * @file 012.左右两边子数组的和相等.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-09
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    cout << "[";
    while (it != t.end() - 1) {
        cout << *it++ << ", ";
    }
    cout << *it++ << "]";
    cout << endl;
}

class Solution
{
public:
    int pivotIndex(vector<int> &nums)
    {
        // 左区间和+nums[i]+右区间和=总和
        // 且左区间和==右区间和
        // 因此 2*左区间和+nums[i]=总和
        int n = nums.size();
        int leftSum = 0;
        int totalSum = 0;
        for (int i = 0; i < n; ++i) {
            totalSum += nums[i];
        }
        for (int i = 0; i < n; ++i) {
            if (2 * leftSum + nums[i] == totalSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
};

int main()
{
    vector<int> nums1 = {1, 7, 3, 6, 5, 6};
    vector<int> nums2 = {1, 2, 3};
    vector<int> nums3 = {2, 1, -1};
    cout << Solution().pivotIndex(nums1) << endl; // 3
    cout << Solution().pivotIndex(nums2) << endl; // -1
    cout << Solution().pivotIndex(nums3) << endl; // 0
    return 0;
}